#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
    struct Compare {
        bool operator()(const pair<int,int>& left, const pair<int,int>& right) {
            return left.second > right.second;
        }
    };

public:
    int shortestBridge(vector<vector<int>>& A) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, Compare>queue_;
        unordered_set<int>visited;
        int row = A.size();
        int col = A[0].size();
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < A[i].size(); ++j) {
                if (A[i][j] == 1) {
                    queue_.push(make_pair<int, int>(i * col + j, 0));
                    visited.emplace(i * col + j);
                    break;
                }
            }
            if (!queue_.empty())
                break;
        }
        vector<vector<int>>ops = { {1,0},{-1,0},{0,1},{0,-1} };
        while (!queue_.empty()) {
            auto point = queue_.top();
            queue_.pop();
            for (auto& op : ops) {
                int i = point.first / col + op[0];
                int j = point.first % col + op[1];
                if (i < 0 || i >= row || j < 0 || j >= col)
                    continue;
                int key = i * col + j;
                if (visited.find(key) != visited.end())
                    continue;
                int cost = point.second + 1;
                if (A[point.first / col][point.first % col] != 1 && A[i][j] == 1)
                    return point.second;
                visited.emplace(key);
                if (A[i][j] == 1) {
                    cost = 0;
                    queue_.push(point);
                }
                queue_.push(make_pair<int, int>(std::move(key), std::move(cost)));
            }
        }
        return 1;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> A = { {0,0,1,1,1,1},{0,0,1,0,1,0},{0,0,0,1,0,0},{0,0,0,1,1,0},{0,0,0,0,1,0},{0,0,0,0,0,0} };
    sol.shortestBridge(A);
}